Motivation

Given a set of $n$ points $P$ on a real line and a query interval $[x:x’]$ find all the points inside the interval.

Construct a binary search tree from $P$ and perform the following query:

Figure: Example of searching in range tree

• Search for $x$ and $x’$ until we get to $v_{\rm split}$ where the search path splits.
• From the left child of $v_{\rm split}$ we continue search with $x$ and at every node $v$ we where search path goes left we all points in right subtree of $v$.
• Symmetrically we go right from $v_{\rm split}$ searching for $x’$ and taking left subtrees of $v$ respectively.

Definition

Canonical Subset of node $v$ (i.e. $P(v)$): subset of points stored in the leaves of the subtree at $v$.

2-D Range Trees

• The main tree is a balanced binary search tree built $T$ built on the x-coordinates of $P$.
• For any internal node / leaf node $v$ in $T$, the canonical subset $P(v)$ is stored in a balanced binary search tree $T_1(v)$ on the y-coordinates of the points. The node $v$ contains a pointer to the root of $T_1(v)$.

Creation $O(n\log n)$

Note Use presorted $P$

• Create $T_1(v)$ binary search tree.
• If $P$ has only one point then create leaf else split $P$ into two sets $P_{\rm left}$ and $P_{\rm right}$ using $x_{\rm mid}$ median point. Recursively create $v_{\rm left}$ and $v_{\rm right}$ from $P_{\rm left}$ and $P_{\rm right}$ respectively. Create a node with $x_{\rm mid}$ and $v_{\rm left}$ and $v_{\rm right}$ left and right children of this node. Make $T_1(v)$ the associated structure of $v$.

Querying $O(\log ^2n +k)$

• Find $v_{\rm split}$
• If $v_{\rm split}$ is a leaf check point inside it and report if necessary.
• Else
  • Follow path to $x$ and perform 1-D range query on the subtrees right of the path. Also check if point stored at the final leaf node $v$ must be reported.
  • Similary do for $x’$ and perform 1-D range query on the subtrees left of the path from $v_{\rm split}$. Again check at the end for the point stored at $v$.

Fractional Cascading

If two sets of objects $S_1$ and $S_2$ are stored int sorted arrays $A_1$ and $A_2$. To find keys in $[y:y’]$

• We can binary search for ceil of $y$ in $A_1$ and then walk along the array until the floor of $y’$. Similary for $S_2$. Total time will be $O(k)$ plus two binary searches ($k$ reported objects).
• If $S_2\subseteq S_1$ we can maintain pointers from $A_1$ to $A_2$, i.e. we store the pointer to ceil key for every value in $A_1$. This will avoid the second binary search.

Figure: Layered Range Tree showing only x-coordinates. Full points are given below

Similarly $P(lc(v))\subseteq P(v)$ and $P(rc(v))\subseteq P(v)$. Instead of associated binary trees we will store an array sorted on the y-coordinates. Each value in the array will additionaly store two pointers to $A(lc(v))$ and $A(rc(v))$. This becomes the layered range tree. This makes the query time $O(\log n + k)$.

Figure: The associated arrays with the nodes.

While querying for $[x:x’]\times[y:y’]$:

• We search for $x$, $x’$ and $v_{\rm split}$. At $A(v_{\rm split})$ we we find the ceil entry of $y$.
• While searching in $x$ and $x’$ in main tree we keep track of ceil entry of $y$ by following pointers in constant time.